package com.cjm.algorithm.backtracking;

import java.util.*;

public class Ti78 {
    public static void main(String[] args) {
        Ti78 ti78 = new Ti78();
        //List<List<Integer>> subsets = ti78.subsetsA(new int[]{1,2,3,4,5,6,7,8,10,0});
        List<List<Integer>> subsets = ti78.subsetsA(new int[]{1,2,3});

        System.err.println("OK");
    }

    public List<List<Integer>> subsetsA(int[] nums) {
        res.clear();
        path.clear();
        method78a(nums, 0);
        return res;
    }

    private void method78a(int[] nums, int startIndex) {
        res.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            path.addLast(nums[i]);
            method78a(nums, i+1);
            path.removeLast();
        }
    }


    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        res.clear();
        path.clear();
        dup.clear();
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length; i++) {
            method78(nums, 0, i);
        }
        return res;
    }

    Map<String, Integer> dup = new HashMap<>();
    private void method78(int[] nums, int startIndex, int size) {
        if (path.size() == size) {
            ArrayList<Integer> e = new ArrayList<>(path);
            StringBuilder sb = new StringBuilder();
            Collections.reverse(e);
            for (Integer i : e) {
                sb.append(i);
            }
            if (dup.get(sb.toString()) == null) {
                res.add(e);
                dup.put(sb.toString(), 1);
            }
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            path.addFirst(nums[i]);
            method78(nums, i+1, size);
            path.removeFirst();
            method78(nums, i+1, size);
        }
    }
}
